package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
 *
 * 给定一个二叉树，找出其最小深度。
 *
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 *
 * 说明：叶子节点是指没有子节点的节点。
 *
 * @author hanjuntao
 * @date 2025/8/28 0028
 */
public class L_111_二叉树的最小深度 {


    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.left.left = new TreeNode(3);
        root2.left.left.left = new TreeNode(4);

        System.out.println(minDepth(root2));
    }

    /**
     * 从题意可知，最小深度指的是从根点到叶子节点的最短距离
     *
     * 可以找到 左右子树的最小深度，然后取最小值，然后加上当前根接单
     *
     * minDepth = {
     *     1. 如果左子树为空，则返回右子树的最小深度 + 1
     *     2. 如果右子树为空，则返回左子树最小深度 + 1
     *     3. 否则，返回左右子树最小深度 + 1
     * }
     *
     * 这里注意一点，需要判断左右子树是否为空，因为为空的话，深度是0，0与其他值比较取最小值，就会返回0，导致计算出错误
     *
     * 终止条件：
     * 1. 节点为空， 返回0
     * 2. 节点是叶子节点，返回1
     *
     *
     * @param root
     * @return
     */
    public static int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 如果是叶子节点，则返回1，因为是最小深度
        if (root.left == null && root.right == null) {
            return 1;
        }

        // 找左右字数树的最小深度
        // 这里注意一点，需要判断左右子树是否为空，因为为空的话，深度是0，0与其他值比较取最小值，就会返回0，导致计算出错误
        if (root.left == null) {
            return minDepth(root.right) + 1;
        }
        if (root.right == null) {
            return minDepth(root.left) + 1;
        }
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}
